home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / compress.zoo / compapi.c next >
C/C++ Source or Header  |  1989-06-30  |  22KB  |  682 lines
  1. /*@H************************ < COMPRESS API    > ****************************
  2. *                                                                           *
  3. *   compress : compapi.c  <current version of compress algorithm>           *
  4. *                                                                           *
  5. *   port by  : Donald J. Gloistein                                          *
  6. *                                                                           *
  7. *   Source, Documentation, Object Code:                                     *
  8. *   released to Public Domain.  This code is based on code as documented    *
  9. *   below in release notes.                                                 *
  10. *                                                                           *
  11. *---------------------------  Module Description  --------------------------*
  12. *   Contains source code for modified Lempel-Ziv method (LZW) compression   *
  13. *   and decompression.                                                      *
  14. *                                                                           *
  15. *   This code module can be maintained to keep current on releases on the   *
  16. *   Unix system. The command shell and dos modules can remain the same.     *
  17. *                                                                           *
  18. *--------------------------- Implementation Notes --------------------------*
  19. *                                                                           *
  20. *   compiled with : compress.h compress.fns compress.c                      *
  21. *   linked with   : compress.obj compusi.obj                                *
  22. *                                                                           *
  23. *   problems:                                                               *
  24. *                                                                           *
  25. *                                                                           *
  26. *   CAUTION: Uses a number of defines for access and speed. If you change   *
  27. *            anything, make sure about side effects.                        *
  28. *                                                                           *
  29. * Compression:                                                              *
  30. * Algorithm:  use open addressing double hashing (no chaining) on the       *
  31. * prefix code / next character combination.  We do a variant of Knuth's     *
  32. * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime     *
  33. * secondary probe.  Here, the modular division first probe is gives way     *
  34. * to a faster exclusive-or manipulation.                                    *
  35. * Also block compression with an adaptive reset was used in original code,  *
  36. * whereby the code table is cleared when the compression ration decreases   *
  37. * but after the table fills.  This was removed from this edition. The table *
  38. * is re-sized at this point when it is filled , and a special CLEAR code is *
  39. * generated for the decompressor. This results in some size difference from *
  40. * straight version 4.0 joe Release. But it is fully compatible in both v4.0 *
  41. * and v4.01                                                                 *
  42. *                                                                           *
  43. * Decompression:                                                            *
  44. * This routine adapts to the codes in the file building the "string" table  *
  45. * on-the-fly; requiring no table to be stored in the compressed file.  The  *
  46. * tables used herein are shared with those of the compress() routine.       *
  47. *                                                                           *
  48. *     Initials ---- Name ---------------------------------                  *
  49. *      DjG          Donald J. Gloistein, current port to MsDos 16 bit       *
  50. *                   Plus many others, see rev.hst file for full list        *
  51. *      LvR          Lyle V. Rains, many thanks for improved implementation  *
  52. *                   of the compression and decompression routines.          *
  53. *************************************************************************@H*/
  54.  
  55. #include <stdio.h>
  56.  
  57. #include "compress.h" /* contains the rest of the include file declarations */
  58.  
  59. static int offset;
  60. static long int in_count ;         /* length of input */
  61. static long int bytes_out;         /* length of compressed output */
  62.  
  63. static CODE prefxcode, nextfree;
  64. static CODE highcode;
  65. static CODE maxcode;
  66. static HASH hashsize;
  67. static int  bits;
  68.  
  69.  
  70. /*
  71.  * The following two parameter tables are the hash table sizes and
  72.  * maximum code values for various code bit-lengths.  The requirements
  73.  * are that Hashsize[n] must be a prime number and Maxcode[n] must be less
  74.  * than Maxhash[n].  Table occupancy factor is (Maxcode - 256)/Maxhash.
  75.  * Note:  I am using a lower Maxcode for 16-bit codes in order to
  76.  * keep the hash table size less than 64k entries.
  77.  */
  78. CONST HASH hs[] = {
  79.   0x13FF,       /* 12-bit codes, 75% occupancy */
  80.   0x26C3,       /* 13-bit codes, 80% occupancy */
  81.   0x4A1D,       /* 14-bit codes, 85% occupancy */
  82.   0x8D0D,       /* 15-bit codes, 90% occupancy */
  83.   0xFFD9        /* 16-bit codes, 94% occupancy, 6% of code values unused */
  84. };
  85. #define Hashsize(maxb) (hs[(maxb) -MINBITS])
  86.  
  87. CONST CODE mc[] = {
  88.   0x0FFF,       /* 12-bit codes */
  89.   0x1FFF,       /* 13-bit codes */
  90.   0x3FFF,       /* 14-bit codes */
  91.   0x7FFF,       /* 15-bit codes */
  92.   0xEFFF        /* 16-bit codes, 6% of code values unused */
  93. };
  94. #define Maxcode(maxb) (mc[(maxb) -MINBITS])
  95.  
  96. #ifdef __STDC__
  97. #ifndef NDEBUG
  98. #define allocx(type, ptr, size) \
  99.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),(unsigned int)sizeof(type))) == NULLPTR(type) \
  100.     ?   (fprintf(stderr,"%s: "#ptr" -- ", prog_name), NOMEM) : OK \
  101.     )
  102. #else
  103. #define allocx(type,ptr,size) \
  104.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),(unsigned int)sizeof(type))) == NULLPTR(type) \
  105.     ? NOMEM : OK \
  106.     )
  107. #endif
  108. #else
  109. #define allocx(type,ptr,size) \
  110.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),(unsigned int)sizeof(type))) == NULLPTR(type) \
  111.     ? NOMEM : OK \
  112.     )
  113. #endif
  114.  
  115. #define free_array(type,ptr,offset) \
  116.     if (ptr != NULLPTR(type)) { \
  117.         efree((ALLOCTYPE FAR *)((ptr) + (offset))); \
  118.         (ptr) = NULLPTR(type); \
  119.     }
  120.  
  121.   /*
  122.    * Macro to allocate new memory to a pointer with an offset value.
  123.    */
  124. #define alloc_array(type, ptr, size, offset) \
  125.     ( allocx(type, ptr, (size) - (offset)) != OK \
  126.       ? NOMEM \
  127.       : (((ptr) -= (offset)), OK) \
  128.     )
  129.  
  130. static char FAR *sfx = NULLPTR(char) ;
  131. #define suffix(code)     sfx[code]
  132.  
  133.  
  134. #if (SPLIT_PFX)
  135.   static CODE FAR *pfx[2] = {NULLPTR(CODE), NULLPTR(CODE)};
  136. #else
  137.   static CODE FAR *pfx = NULLPTR(CODE);
  138. #endif
  139.  
  140.  
  141. #if (SPLIT_HT)
  142.   static CODE FAR *ht[2] = {NULLPTR(CODE),NULLPTR(CODE)};
  143. #else
  144.   static CODE FAR *ht = NULLPTR(CODE);
  145. #endif
  146.  
  147.  
  148. #ifdef __STDC__
  149. int alloc_tables(CODE maxcode, HASH hashsize)
  150. #else
  151. int alloc_tables(maxcode, hashsize)
  152.   CODE maxcode;
  153.   HASH hashsize;
  154. #endif
  155. {
  156.   static CODE oldmaxcode = 0;
  157.   static HASH oldhashsize = 0;
  158.  
  159.   if (hashsize > oldhashsize) {
  160. #if (SPLIT_HT)
  161.       free_array(CODE,ht[1], 0);
  162.       free_array(CODE,ht[0], 0);
  163. #else
  164.       free_array(CODE,ht, 0);
  165. #endif
  166.     oldhashsize = 0;
  167.   }
  168.  
  169.     if (maxcode > oldmaxcode) {
  170. #if (SPLIT_PFX)
  171.         free_array(CODE,pfx[1], 128);
  172.         free_array(CODE,pfx[0], 128);
  173. #else
  174.         free_array(CODE,pfx, 256);
  175. #endif
  176.         free_array(char,sfx, 256);
  177.  
  178.         if (   alloc_array(char, sfx, maxcode + 1, 256)
  179. #if (SPLIT_PFX)
  180.             || alloc_array(CODE, pfx[0], (maxcode + 1) / 2, 128)
  181.             || alloc_array(CODE, pfx[1], (maxcode + 1) / 2, 128)
  182. #else
  183.             || alloc_array(CODE, pfx, (maxcode + 1), 256)
  184. #endif
  185.         ) {
  186.             oldmaxcode = 0;
  187.             exit_stat = NOMEM;
  188.             return(NOMEM);
  189.         }
  190.         oldmaxcode = maxcode;
  191.     }
  192.     if (hashsize > oldhashsize) {
  193.         if (
  194. #if (SPLIT_HT)
  195.             alloc_array(CODE, ht[0], (hashsize / 2) + 1, 0)
  196.             || alloc_array(CODE, ht[1], hashsize / 2, 0)
  197. #else
  198.             alloc_array(CODE, ht, hashsize, 0)
  199. #endif
  200.         ) {
  201.             oldhashsize = 0;
  202.             exit_stat = NOMEM;
  203.             ret